package problem;

public class S_109 {
    //将有序链表转换为二叉搜索树

      public class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    class Solution {
          private ListNode node;
        public TreeNode sortedListToBST(ListNode head) {
            int n=0;
            node=head;
            while(head!=null){
                head=head.next;
                n++;
            }
            return toBST(0,n-1);
        }
        private TreeNode toBST(int left,int right){
            if(left>right) return null;
            int mid=left+(right-left)/2;
            TreeNode lchild=toBST(left,mid-1);
            TreeNode father=new TreeNode(node.val);
            node=node.next;
            father.left=lchild;
            father.right=toBST(mid+1,right);
            return father;
        }
    }

    //快慢指针
    class Solution1 {
        //快慢指针
        public TreeNode sortedListToBST(ListNode head) {
            if (head == null) return null;
            if (head.next == null) return new TreeNode(head.val);
            // p 一次前进一格，q 前进两格，pre 是 p 前一个
            ListNode p = head.next, q = head.next.next, pre = head;
            while (q != null && q.next != null) {
                pre = pre.next;
                p = p.next;
                q = q.next.next;
            }
            pre.next = null;
            // 链表被分成三段，再递归构造
            TreeNode root = new TreeNode(p.val);

            root.left  = sortedListToBST(head);

            root.right = sortedListToBST(p.next);

            return root;
        }
    }
}
